package main

import (
	"fmt"
	"strings"
)

type Node struct {
	E    int
	Next *Node
}

type List struct {
	dummyHead *Node
	size      int
}

func (l List) Head() *Node {
	return l.dummyHead
}

func (l List) Size() int {
	return l.size
}

func InitNode(e int) *Node {
	return &Node{
		e,
		nil,
	}
}

func InitList() *List {
	return &List{
		dummyHead: InitNode(0),
		size:      0,
	}
}

func (l *List) IsEmpty() bool {
	return l.size == 0
}

func (l *List) AddIndex(index, e int) {
	if index > l.size || index < 0 {
		panic("索引越界，不能插入了")
	}
	prev := l.dummyHead
	node := InitNode(e)

	for i := 0; i < index; i++ {
		prev = prev.Next
	}
	node.Next = prev.Next
	prev.Next = node
	l.size++
}

func (l *List) AddFirst(e int) {
	l.AddIndex(0, e)
}

func (l *List) AddLast(e int) {
	l.AddIndex(l.size, e)
}

func (l *List) Get(index int) int {
	if index > l.size || index < 0 {
		panic("索引越界，不能查询")
	}
	cur := l.dummyHead.Next
	for i := 0; i < index; i++ {
		cur = cur.Next
	}
	return cur.E
}

func (l *List) GetFirst() int {
	return l.Get(0)
}

func (l *List) GetLast() int {
	return l.Get(l.size - 1)
}

func (l *List) Set(index, e int) {
	if index > l.size || index < 0 {
		panic("索引越界,不能写入")
	}
	cur := l.dummyHead.Next
	for i := 0; i < index; i++ {
		cur = cur.Next
	}
	cur.E = e
}

func (l *List) Contains(e int) bool {
	cur := l.dummyHead.Next
	for cur != nil {
		if cur.E == e {
			return true
		}
		cur = cur.Next
	}
	return false
}

// 在链表中删除元素
func (l *List) Remove(index int) int {
	if index > l.size || index < 0 {
		panic("索引越界，不能删除")
	}
	prev := l.dummyHead
	for i := 0; i < index; i++ {
		prev = prev.Next
	}
	retNode := prev.Next
	prev.Next = retNode.Next
	l.size--
	return retNode.E
}
func (l *List) RemoveFirst() int {
	return l.Remove(0)
}
func (l *List) RemoveLast() int {
	return l.Remove(l.size - 1)
}

// 删除元素 E
func (l *List) RemoveElement(e int) {
	prev := l.dummyHead
	for prev.Next != nil {
		if prev.Next.E == e {
			break
		}
		prev = prev.Next
	}
	if prev.Next != nil {
		DelNode := prev.Next
		prev.Next = DelNode.Next
		DelNode = nil
	}
}

// 在Golang中，如果我们想对自建数据结构自定义在Println的时候打印出什么结果
// 就可以使用这种方式去自己构建打印的字符串格式
func (l *List) String() string {
	var builder strings.Builder
	cur := l.dummyHead.Next
	for cur != nil {
		fmt.Fprintf(&builder, "%d -> ", cur.E)
		cur = cur.Next
	}
	fmt.Fprintf(&builder, "NULL")
	return builder.String()
}
